package com.xyhuo.leetcode.december;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 字符串相乘
 * https://leetcode.cn/problems/multiply-strings/
 *
 * @time 2023/12/18
 */
public class Multiply {

//    public static void main(String[] args) {
//        Multiply multiply = new Multiply();
//        multiply.multiply("67", "89");
//    }

    public String multiply(String num1, String num2) {
        String zero = "0";
        if (num1.equals(zero) || num2.equals(zero)) {
            return zero;
        }
        List<Integer> num1List = toIntArray(num1);
        List<Integer> num2List = toIntArray(num2);
        List<Deque<Integer>> sumList = new ArrayList<>();
        int num2Len = num2List.size();
        for (int i = 0; i < num2Len; i++) {
            Deque<Integer> listItem = multiply(num1List, num2List.get(num2Len - 1 - i), i);
            sumList.add(listItem);
        }
        String ans = plusNum(sumList);
        return ans;
    }

    private Deque<Integer> multiply(List<Integer> list, int num, int zero) {
        Deque<Integer> ans = new ArrayDeque<>();
        while (zero > 0) {
            ans.add(0);
            zero--;
        }
        int plus = 0;
        int size = list.size();
        for (int i = 0; i < size; i++) {
            Integer last = list.get(size - 1 - i);
            int tmp = last * num + plus;
            int val = tmp % 10;
            ans.addFirst(val);
            plus = tmp / 10;
        }
        if (plus != 0) {
            ans.addFirst(plus);
        }
        return ans;
    }

    private String plusNum(List<Deque<Integer>> list) {
        Deque<Integer> ans = new ArrayDeque<>();

        int plus = 0;
        while (true) {
            int emptyCount = 0;
            for (int i = 0; i < list.size(); i++) {
                Deque<Integer> deque = list.get(i);
                if (!deque.isEmpty()) {
                    Integer last = deque.removeLast();
                    plus += last;
                } else {
                    emptyCount++;
                }
            }
            if (emptyCount == list.size()) {
                break;
            }
            int val = plus % 10;
            ans.addFirst(val);
            plus = plus / 10;
        }

        if (plus != 0) {
            ans.addFirst(plus);
        }

        StringBuilder sb = new StringBuilder();
        while (!ans.isEmpty()) {
            sb.append(ans.removeFirst());
        }
        return sb.toString();
    }

    private List<Integer> toIntArray(String num) {
        char[] charArray = num.toCharArray();
        List<Integer> numList = new ArrayList<>();
        for (int i = 0; i < charArray.length; i++) {
            numList.add(charArray[i] - '0');
        }
        return numList;
    }
}
